33C - Wonderful Randomized Sum - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;



int main(){
	
	int n;
	cin>>n;

	int arr[n];
	

	int VACSuffix[n];
	int MVASuffix[n];

	int VACPrefix[n];
	int MVAPrefix[n];

	int val;
	cin>>val;
	arr[0] = val;
	VACPrefix[0] = val;
	if(val<0){
		MVAPrefix[0] = val;
	}
	else {
		MVAPrefix[0] = 0;
	}

	for (int i = 1; i < n; ++i)
	{
		int val;
		cin>>val;
		arr[i]=val;
		VACPrefix[i] = VACPrefix[i-1]+val;
		if(MVAPrefix[i-1] > VACPrefix[i]){
			MVAPrefix[i] = VACPrefix[i];
		}
		else{
			MVAPrefix[i] = MVAPrefix[i-1];
		}
	}

	if(n==2){
		int result = abs(arr[0])+abs(arr[1]);
		cout<<result<<endl;
		return 0;
	}

	VACSuffix[n-1] = arr[n-1];
	if(arr[n-1]<0){
		MVASuffix[n-1] = arr[n-1];
	}
	else{
		MVASuffix[n-1] = 0;
	}
	
	for (int i = n-2; i >=0 ; --i)
	{
		VACSuffix[i] = VACSuffix[i+1]+arr[i];
		if(MVASuffix[i+1] > VACSuffix[i]){
			MVASuffix[i] = VACSuffix[i];
		}
		else{
			MVASuffix[i] = MVASuffix[i+1];
		}
	}
	int maxSum = 0;
	for (int i = 0; i < n-1; ++i)
	{
		if(maxSum > MVASuffix[i+1]+MVAPrefix[i]){
			maxSum =  MVASuffix[i+1]+MVAPrefix[i];
		}
	}
	int maxVal = VACPrefix[n-1];
	maxVal = max(maxVal,-VACPrefix[n-1]);
	maxVal = max(maxVal, VACPrefix[n-1]-2* maxSum);

	cout<<maxVal<<endl;
	return 0;
}